模拟赛题解/2025.8.21 模拟赛

T1-钢（hoi）

题面

一棵树上有 $n$ 个点，每个点上初始权值为 $1$。

两人先后选择一个点清除，并使其他所有点上的权值向这个点迁移一次。

当最后一个点被清除后，清除掉最后一个点的人获胜。

问在都选择最优策略的情况下，谁能获胜。

$1\leq n\leq2\times10^5$

题解

可以将清除这一过程转化为树上所有除了所选的点之外的叶子节点被删除。

考虑树上的一条条链，每次变化会使树上的链长度减少 $1$ 或 $2$，显然直径会最后被删完。

因此只需要考虑直径，将每次操作转化为使链长减少 $1$ 或 $2$，这就是一道经典的小学奥数题。

T2-蒸（sgs）

题面

有一条长为 $n$，由 $A,B,C$ 三种字符构成的字符串。

每次操作可以删除任意一个形如 $AB,CA,AACB,AAA,CCB$ 之一的子序列。

如果能删除整个序列，就可以获得 $p^a\times q^b\times r^c$ 的值，$p,q,r$ 给出，$a,b,c$ 分别代表字符串中 $A,B,C$ 的数量。

给出 $n$，求对于所有数量为 $1\sim n$ 的起始字符串长度，可以得到的值的和。

题解

对于这样的字符串删除，考虑将其转换为字符串匹配（什么神仙思路）。

观察到对于所有可删除的子序列，$B$ 都在末尾，将其转化为右括号。

因为存在 $CCB$，所以我们将 $C$ 转化为一个左括号，将 $B$ 转化为两个右括号。

又因为存在 $AB,CA,AAA$，所以考虑将 $A$ 转化为两个左括号或者一个右括号，代入 $AACB$ 发现没问题。

又因为若存在两个 $A$ 将前一个当作左括号，后一个当作右括号一定是没问题的。

于是设 $f_{i,j,0/1}$ 表示当前填充到第 $i$ 位，剩余 $j$ 个左括号， 目前是否出现过被当成右括号的 $A$ 的情况下的最大权值和，转移是不难的。

T3-原（gen）

题面

有一个长度为 $n$ 的序列 $a$，可以进行若干次操作，每次操作形如 $op,l,r$，可以将 $[a_l,a_r]$ 的所有数改为 $a_l$ 或 $a_r$，若 $op$ 为 $L$ 则将区间改为 $a_l$，若为 $R$ 则改为 $a_r$。

如果能将序列更改为给定的序列 $b$ 则视为获胜，求出是否能获胜，如果能，给出操作方案，要求操作次数不超过 $n$。

$1\leq n\leq3\times10^5,1\leq a_i,b_i\leq3\times10^5$

题解

首先，根据操作的性质，我们注意到不可能将形如 $ab$ 的序列转换为 $ba$，即不能改变数字间的顺序。

因此我们只需要能在 $a$ 序列中找到一个顺序包含 $b$ 序列中所有数的子序列则有解。

考虑如何构造方案，可以将 $a$ 中的子序列和 $b$ 中对应区间分类考虑，设 $a$ 中位置为 $pos_i$，$b$ 中对应区间为 $l_i,r_i$。

1. $pos_i<l_i$，此时将 $[l_i,r_i]$ 一次覆盖完之后必须要让其他数字覆盖 $[pos_i,l_i-1]$ 的区间。
2. $pos_i>r_i$，此时将 $[l_i,r_i]$ 一次覆盖完之后必须要让其他数字覆盖 $[r_i+1,pos_i]$ 的区间。
3. $l_i\leq pos_i\leq r_i$，此时只需要用一次（$pos_i=l_i$ 或 $pos_i=r_i$）或两次（$l_i<pos_i<r_i$）将 $[l_i,r_i]$ 覆盖完即可。

并且，因为 $pos$ 和 $l_i,r_i$ 是单调递增的，因此构成一定是一段前缀属于情况 $1$，一段后缀属于情况 $2$，其余部分属于情况 $3$。

因此我们构造情况 $1$ 为按 $pos$ 递减顺序做，情况 $2$ 为按 $pos$ 递增顺序做，情况 $3$ 可以随便做。

证明操作次数：我们考虑到，对于 $pos_i$ 需要做两次的情况当且仅当 $l_i<pos_i<r_i$，但此时实际上覆盖了长度至少为 $3$ 的区间，而其他情况下都只需要做一次操作，$pos$ 不会出现重复，所以总的操作次数一定不超过 $n$。

T4-诡（lom）

题面

有一个长度为 $n$ 的序列 $a$，要将其划分为若干（$\geq2$）个区间，每个划分方案的贡献是所有区间的极差之和。

每次操作将选择一段区间并将该区间内所有数增加 $x$，并求出每次修改后的最大划分贡献，询问不独立。

$1\leq n,q\leq2\times10^5,-10^8\leq a_i,x\leq10^8$

题解

考虑原序列的差分序列，显然可以发现当取到最大值时需要使一段区间内全部同正或同负。

那么只需要考虑每段差分序列的左右两边是否被选既可。

每次操作相当于两次单点修改，使用小清新线段树即可通过。